package org.basis.algorithm.list.practice;

import org.basis.algorithm.list.common.SingleNode;

import java.util.HashSet;

/**
 * 链表找环练习
 *
 * @author Mr_wenpan@163.com 2021/12/15 11:27
 */
public class ListFindLoop2 {

    public static void main(String[] args) {

    }

    public static boolean hasLoop1(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return false;
        }

        HashSet<SingleNode<Integer>> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return true;
            }
            set.add(head);
            head = head.next;
        }

        return false;
    }

    public static boolean hasLoop2(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return false;
        }
        SingleNode<Integer> fast = head.next;
        SingleNode<Integer> slow = head;

        while (fast != null) {
            if (fast == slow) {
                return true;
            }
            fast = fast.next == null ? null : fast.next.next;
            slow = slow.next;
        }

        return false;
    }

    public static SingleNode<Integer> findLoop1(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return null;
        }
        HashSet<SingleNode<Integer>> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }

    public static SingleNode<Integer> findLoop2(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return null;
        }
        SingleNode<Integer> fast = head.next;
        SingleNode<Integer> slow = head;
        boolean hasLoop = false;
        while (fast != null) {
            if (fast == slow) {
                hasLoop = true;
                break;
            }
            slow = slow.next;
            fast = fast.next == null ? null : fast.next.next;
        }

        if (!hasLoop) {
            return null;
        }

        // 寻找入环节点
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }

}
